enum List {
    // 元组, 包括链表的一个元素和指向下个节点的指针 (Box装箱)
    Cons(u32, Box<List>),
    // Nil 末结点,表示链表结束
    Nil,
}

// 给链表增加函数
impl List {
    // 创建一个空链表
    fn new() -> List {
        List::Nil
    }

    // 头部插入一个元素, 返回链表
    fn insert(self, u: u32) -> List {
        // Cons 为 List 类型
        List::Cons(u, Box::new(self))
    }

    // 链表长度
    fn len(&self) -> u32 {
        // & 借用
        match *self {
            // 解引用
            List::Cons(_, ref tail) => 1 + tail.len(), // 调用下一节点的 len 直到 match 到 Nil; ref 无法得到所有权,只能用引用
            List::Nil => 0,                            // 末节点, 返回0
        }
    }

    // 返回链表字串
    fn stringify(&self) -> String {
        match *self {
            List::Cons(head, ref tail) => format!("{}, {}", head, tail.stringify()),
            List::Nil => "".to_string(),
        }
    }
}

fn main() {
    println!("链表");

    // new
    let mut list = List::new();
    list = list.insert(5);
    list = list.insert(4);
    list = list.insert(3);
    list = list.insert(2);
    list = list.insert(1);
    println!("len: {}", list.len());
    println!("stringify: {}", list.stringify());
}
